max_val = 10 ** 5 + 1
zhishu = []
st = [i for i in range(max_val)]
for i in range(2, max_val):
    if st[i] == i:
        zhishu.append(i)
    for num in zhishu:
        if num * i < max_val:
            st[num * i] = num
        else:
            break
        if i % num == 0:
            break


class Solution(object):
    def largestComponentSize(self, nums):
        p = {num: num for num in zhishu}
        rank = {num: 0 for num in zhishu}
        p[1] = 1
        rank[1] = 0
        def find(x):
            if p[x] == x:
                return p[x]
            else:
                p[x] = find(p[x])
                return p[x]

        def union(x, y):
            rx = find(x)
            ry = find(y)
            if rx != ry:
                if rx > ry:
                    p[rx] = ry
                    rank[ry] += rank[rx]
                    rank[rx] = 0
                else:
                    p[ry] = rx
                    rank[rx] += rank[ry]
                    rank[ry] = 0

        for num in nums:
            if st[num] == num:
                rank[p[num]] += 1
            else:
                base = p[st[num]]
                rank[base] += 1
                num = num // st[num]
                while num > 1:
                    union(base, st[num])
                    num = num // st[num]

        for num in rank:
            if rank[num] and find(num) != num:
                rank[find(num)] += rank[num]
                rank[num] = 0
        return max(rank.values())


data = Solution()
nums = [2, 3, 6, 7, 4, 12, 21, 39]
print(data.largestComponentSize(nums))
